package heap;

import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class leetcode313超级丑数 {
    // 堆
    // 存在问题：维护小根堆时间复杂度大
    // 计算相当多无效值，空间复杂度大
    public int nthSuperUglyNumber(int n, int[] primes) {
        PriorityQueue<Long> queue = new PriorityQueue<>();
        Set<Long> set = new HashSet<>();
        queue.offer(1L);
        set.add(1L);
        int index = 1;
        while (index < n) {
            int length = primes.length;
            Long poll = queue.poll();
            for (int i = 0; i < length; i++) {
                Long num = poll * primes[i];
                if (!set.contains(num)) {
                    queue.offer(num);
                    set.add(num);
                }
            }
            index++;
        }
        long result = queue.peek();
        return (int) result;
    }

    public int nthSuperUglyNumber1(int n, int[] primes) {
        int length = primes.length;
        int[] pointers = new int[length];
        Arrays.fill(pointers, 0);
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < length; j++) {
                min = Integer.min(dp[pointers[j]] * primes[j], min);
            }
            dp[i] = min;
            for (int j = 0; j < length; j++) {
                if (dp[pointers[j]] * primes[j] == min) {
                    pointers[j]++;
                }
            }
        }
        return dp[n - 1];
    }
}
